#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <functional>

using namespace std;


// 使用二叉堆实现优先级队列
// 二叉堆的实现
// 二叉堆的插入和删除操作
// 二叉堆的堆化操作
// 二叉堆的堆排序操作

class binaryheapprique
{
public:
    using Comp = std::function<bool(int, int)>;
    binaryheapprique(int capacity, Comp comp = greater<int>())
            :size_(0)
            ,cap_(capacity)
            ,comp_(comp)
    {
        que_ = new int[cap_];
    }

    binaryheapprique()
            :size_(0)
            ,cap_(10)
            ,comp_(greater<int>())
    {
        que_ = new int[cap_];
    }

    ~binaryheapprique()
    {
        delete [] que_;
        que_ = nullptr;
    }
    void push(int value)
    {
        if (size_ == cap_)
        {
            resize(cap_ * 2);
        }

        if (size_ == 0)
        {
            que_[size_] = value;
        }

        else
        {
            shiftUp(size_, value);
        }
        size_++;
    }
    void pop()
    {
        if (size_ == 0)
        {
            throw std::out_of_range("queue is empty");
        }
        // 把最后一个元素放到堆顶
        // 进行下沉
        // que_[0] = que_[size_ - 1];
        // shiftDown(0,que_[size_ - 1]);
        // size_--;
        size_--;
        que_[0] = que_[size_];  //
        if (size_ > 0) shiftDown(0);
    }
    int top()
    {
        if (size_ == 0)
        {
            throw std::out_of_range("queue is empty");
        }
        return que_[0];
    }
    int size()
    {
        return size_;
    }
    bool empty()
    {
        return size_ == 0;
    }

    void show()
    {
        for (int i = 0; i < size_; i++)
        {
            cout << que_[i] << " ";
        }
        cout << endl;
    }

private:
    void resize(int newCap)
    {
        int* tmp_que = new int[newCap];
        for (int i = 0; i < size_; i++)
        {
            tmp_que[i] = que_[i];
        }
        delete [] que_;
        que_ = tmp_que;
        cap_ = newCap;
    }

    void shiftUp(int index, int value)
    {
        // 在堆中插入一个元素，需要从下往上堆化
        // 但是堆化到根节点时为止
        while (index > 0)
        {
            // 根据自身索引，找到父节点的索引
            int parent = (index - 1) / 2;
            // 如果父节点和当前节点满足大根/小根堆（取决于函数对象的实现）的性质，直接跳出循环
            // 因为当前排序是正确的
            if (comp_(que_[parent], value))
            {
                break;
            }
            
            // 否则把父节点的值下沉，节点继续向上堆化
            que_[index] = que_[parent];
            index = parent;
        }
        // 最终放到合适的位置
        que_[index] = value;
    }

    void shiftDown(int index)
    {
        // 从上往下堆化
        // 一直堆化到最后的非叶子节点为止，不需要比较到叶子节点
        int current = index;
        int value = que_[current];
        while (current < size_/2)
        {
            int child = current * 2 + 1;
            if (child+1 < size_ && comp_(que_[child+1], que_[child]))
                child++;
            
            if (comp_(value, que_[child])) break;
            
            que_[current] = que_[child];
            current = child;
        }
        que_[current] = value; 
    }

private:
    int* que_;
    int cap_;
    int size_;
    Comp comp_;
};


// int main(int argc, char const *argv[]) {
//     binaryheapprique que;
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++)
//     {
//         int val = rand() % 1000;
//         que.push(val);
//         // que.show();
//         cout << val << " ";
//     }
//     cout << endl;

//     while (!que.empty())
//     {
//         cout << que.top() << " ";
//         que.pop();
//         // que.show();
//     }
//     cout << endl;

//     return 0;
// }
